Conflict Anticipation in the Search for Graph Automorphisms

摘要

Effective search for graph automorphisms allows identifying symmetries inmany discrete structures, ranging from chemical molecules to microprocessorcircuits. Using this type of structure can enhance visualization as well asspeed up computational optimization and verification. Competitive algorithmsfor the graph automorphism problem are based on efficient partition refinementaugmented with group-theoretic pruning techniques. In this paper, we improveprior algorithms for the graph automorphism problem by introducing simultaneousrefinement of multiple partitions, which enables the anticipation of futureconflicts in search and leads to significant pruning, reducing overallruntimes. Empirically, we observe an exponential speedup for the family ofMiyazaki graphs, which have been shown to impede leading graph-automorphismalgorithms.